package 中等.前缀和与差分;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
 * 返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。
 * 若不存在这样的数组，返回一个空数组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-longest-subarray-lcci
 */
public class 字母与数字_1705 {

    public static void main(String[] args) {

        findLongestSubarray(new String[]{"A", "1", "B", "C", "D", "2", "3", "4", "E", "5", "F", "G", "6", "7", "H", "I", "J", "K", "L", "M"});

    }

    /**
     * 转换题意+前缀和+哈希表
     * 1，连续子数组的字母和数字相等，把字母看作 1 数字
     * 看作 -1 ，题意转换为求和为 0 最长连续子数组
     * 2，假设 i < j ，prefixSum[i] 代表 [0,i] 的和
     * prefixSum[i] == prefixSum[j]
     * 那么 prefix[j] - prefixSum[i] = 0 ，也就是说
     * [i+1,j] 连续子数组的和为 0 ，想要尽可能的长，
     * 就要使得 i 尽可能的小，使用哈希表记录 prefixSum[i]
     * 第一次出现的位置
     */
    public static String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        // 和为 0 的最小索引为 -1
        map.put(0, -1);
        int prefixSum = 0;

        int left = -1, right = -2;
        for (int i = 0; i < array.length; i++) {
            if (Character.isDigit(array[i].charAt(0))) {
                prefixSum--;
            } else {
                prefixSum++;
            }

            if (map.containsKey(prefixSum)) {
                if (i - (map.get(prefixSum) + 1) > right - left) {
                    right = i;
                    left = map.get(prefixSum) + 1;
                }
            } else {
                map.put(prefixSum, i);
            }
        }

        String[] ans = new String[right - left + 1];
        for (int i = left, j = 0; i <= right; i++, j++) {
            ans[j] = array[i];
        }
        return ans;
    }

}
